課程資訊
課程名稱
計算理論
Theory of Computing 
開課學期
109-2 
授課對象
管理學院  資訊管理學系  
授課教師
蔡益坤 
課號
IM3006 
課程識別碼
705 30400 
班次
 
學分
3.0 
全/半年
半年 
必/選修
選修 
上課時間
星期二7,8,9(14:20~17:20) 
上課地點
管二303 
備註
本課程中文授課,使用英文教科書。部份週次之週二6有實習課,地點同上課教室。
總人數上限:40人
外系人數限制:8人 
 
課程簡介影片
 
核心能力關聯
核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

This is an introductory course to the theory of computing, a study of formal/mathematical foundations of computer science and technology. It covers various mathematical models, including automata and Turing machines, for physical computing machineries along with their computational capabilities/limitations. In terms of specific topics and the order of their exposition, the course will follow closely the book by Sipser. 

課程目標
The goal of this course is to acquaint the students with the basic concepts in computation theory and to cultivate the students' ability in analyzing the complexity of computational problems.
 
課程要求
待補 
預期每週課後學習時數
 
Office Hours
每週二 13:30~14:30
每週三 13:30~14:30 
指定閱讀
Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, Cengage Learning, 2013. 
參考書目
See the course wiki site:
http://im.ntu.edu.tw/~tsay/dokuwiki/doku.php?id=courses:theory2020:main 
評量方式
(僅供參考)
 
No.
項目
百分比
說明
1. 
Final 
35% 
 
2. 
Midterm 
35% 
 
3. 
Participation 
10% 
 
4. 
Homework 
20% 
 
 
課程進度
週次
日期
單元主題
第1週
  Introduction and Mathematical Preliminaries 
第2週
  Introduction and Mathematical Preliminaries;
Finite Automata and Regular Languages 
第3週
  Finite Automata and Regular Languages 
第4週
  Finite Automata and Regular Languages 
第5週
  Context-Free Languages and Pushdown Automata 
第6週
  Context-Free Languages and Pushdown Automata 
第7週
  Holiday 
第8週
  Context-Free Languages and Pushdown Automata 
第9週
  Midterm Exam
 
第10週
  Turing Machines 
第11週
  Turing Machines
 
第12週
  Decidability (and Undecidability)
 
第13週
  Decidability (and Undecidability);
Reducibility 
第14週
  Reducibility 
第15週
  Time Complexity and NP-Completeness 
第16週
  Time Complexity and NP-Completeness 
第17週
  Final Exam 
第18週
  More about NP-Completeness;
Wrap-Up Discussions